package 数组和链表.linklist;

import 抽象数据类型.ListNodeData;
import 抽象数据类型.PolynListNode;

public class PolynLinkedList {
    private PolynListNode first = new PolynListNode();
    private int length;


    public PolynLinkedList() {

    }
    //����ѭ������

    public PolynLinkedList CircularLinkedListHead() {
        PolynListNode headNode = first;
        if (first.next != null) {
            PolynListNode currentNode = headNode.next;
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            currentNode.next = headNode.next;
        }
        return new PolynLinkedList(headNode, length);
    }

    public PolynLinkedList CircularLinkedListTail() {
        PolynListNode headNode = first;
        if (first.next != null) {
            PolynListNode currentNode = headNode.next;
            while (currentNode.next != null) {
                currentNode = currentNode.next;
            }
            currentNode.next = headNode.next;
            headNode.next = currentNode;
        }
        return new PolynLinkedList(headNode, length);
    }

    public PolynLinkedList(PolynListNode first, int length) {
        this.first = first;
        this.length = length;
    }

    
    public PolynLinkedList InitList(Object[] L) {
        for (Object o : L) {
            ListInsert(o, length);
        }
        return new PolynLinkedList(first, length);
    }

    
    public void DestroyList() {
        first = null;
    }

    
    public boolean ListEmpty() {
        if (first.next == null) {
            return true;
        }
        return false;
    }

    
    public int ListLength() {
        int count = 0;
        PolynListNode current = first.next;
        while (current != null) {
            current = current.next;
            count++;
        }
        return count;
    }

    
    public Object GetElem(int i) {
        if (i < 0 || i >= this.length) {
            throw new IndexOutOfBoundsException("�±�Խ��");
        }
        int index = 0;
        PolynListNode current = first.next;
        while (true) {
            if (index == i) {
                return current;
            }
            current = current.next;
            index++;
        }
    }

    
    public int LocateElem(Object e) {
        PolynListNode current = first.next;
        int index = 0;
        while (current != null) {
            if (current.getVal().compareTo((ListNodeData) e) == 0) {
                return index;
            }
            current = current.next;
            index++;
        }
        return 0;
    }

    
    public Object PirorElem(Object e) {
        PolynListNode current = first.next;
        PolynListNode priorNode;
        int index = 0;
        while (current != null) {
            priorNode = current;
            if (current.getVal().compareTo((ListNodeData) e) == 0 && index != 0) {
                return priorNode;
            }
            current = current.next;
            index++;
        }
        return null;
    }

    
    public Object nextElem(Object e) {
        PolynListNode current = first.next;
        while (current != null) {
            if (current.getVal().compareTo((ListNodeData) e) == 0) {
                if (current.next != null) {
                    return current.next;
                }
            }
            current = current.next;

        }
        return null;
    }

    
    public void ListInsert(Object e, int i) {
        if (i < 0 || i > length) {
            throw new IndexOutOfBoundsException("����Խ��");
        }

        int index = 0;
        PolynListNode priorNode = first;
        PolynListNode current = first.next;
        PolynListNode insertNode = new PolynListNode((ListNodeData) e);
        if (current == null) {
            first.next = insertNode;
        } else {
            while (current.next != null) {
                if (index == i) {
                    priorNode.next = insertNode;
                    insertNode.next = current.next;
                    return;
                }
                priorNode = current;
                current = current.next;
                index++;
            }
            if (current.next == null) {
                current.next = insertNode;
            }
        }
        this.length++;
    }

    
    public Object ListDelete(int i) {

        if (i < 0 || i >= length) {
            throw new IndexOutOfBoundsException("����Խ��");
        }
        int index = 0;
        PolynListNode priorNode = first;
        PolynListNode current = first.next;
        while (current != null) {
            if (index == i) {
                priorNode.next = current.next;
            }
            priorNode = current;
            current = current.next;
            index++;
        }

        this.length--;
        return current;
    }

    
    public void ListObjectraverse() {
        int count = 40;
        PolynListNode current = first.next;
        while (current != null && count >= 0) {
            count--;
            System.out.print(current.getVal() + "\t");
            current = current.next;
        }

    }

    
    public void Replace(Object e, int i) {
        PolynListNode current = first.next;
        int index = 0;
        while (current != null) {
            if (index == i) {
                current.setVal((ListNodeData) e);
            }
            current = current.next;
            index++;
        }
    }

    static class MainTest {
        public static void main(String[] args) {
            int[] a = {1, 3, 4, 5, 9};
            float[] b = {2, 4, 6, 10, 10};

            ListNodeData[] AListNodeData = new ListNodeData[a.length];
            for (int i = 0; i < a.length; i++) {
                AListNodeData[i] = new ListNodeData(b[i], a[i]);
            }

            int[] ai = {2, 3, 6, 9};
            float[] bi = {2, 4, 6, 10};

            ListNodeData[] BListNodeData = new ListNodeData[ai.length];
            for (int i = 0; i < ai.length; i++) {
                BListNodeData[i] = new ListNodeData(bi[i], ai[i]);
            }

            PolynLinkedList AL = (PolynLinkedList) (new PolynLinkedList()).InitList(AListNodeData);
            PolynLinkedList BL = (PolynLinkedList) (new PolynLinkedList()).InitList(BListNodeData);
            AL.ListObjectraverse();
            System.out.println();
            BL.ListObjectraverse();
            System.out.println();
            AddPolyn(AL, BL).ListObjectraverse();

         /*   LinkedList circularLinkedListHead = AL.CircularLinkedListHead();

            circularLinkedListHead.ListObjectraverse();*/

           /* PolynLinkedList circularLinkedListTailAl = AL.CircularLinkedListTail();
            PolynLinkedList circularLinkedListTailBl = BL.CircularLinkedListTail();
            circularLinkedListTailAl.ListObjectraverse();
            System.out.println();
            MergeListTail(circularLinkedListTailAl, circularLinkedListTailBl).ListObjectraverse();*/
        }

        private static PolynLinkedList MergeListTail(PolynLinkedList La, PolynLinkedList Lb) {
            PolynListNode LaPolynListNode = La.first;
            PolynListNode LbPolynListNode = Lb.first;
            PolynListNode LaTailNode = LaPolynListNode.next;
            PolynListNode LbTailNode = LbPolynListNode.next;
            PolynListNode tempAHead = LaTailNode.next;//ͷ�ڵ�
            LaTailNode.next = LbTailNode.next;
            LbTailNode.next = tempAHead;
            La.first = Lb.first;
            return La;

        }

        private static PolynLinkedList AddPolyn(PolynLinkedList La, PolynLinkedList Lb) {
            PolynListNode headA = La.first.next;
            PolynListNode headB = Lb.first.next;
            PolynListNode prior = La.first;
            while (headA != null && headB != null) {
                PolynListNode insertNode =new PolynListNode(headB.getVal());
                switch (headA.getVal().compareTo(headB.getVal())) {
                    case 0:
                        headA.getVal().setCoef(headA.getVal().getCoef() + headB.getVal().getCoef());
                        prior = headA;
                        headA = headA.next;
                        headB = headB.next;
                        break;
                    case 1:
                        prior.next = insertNode;
                        prior = insertNode;
                        insertNode.next = headA;
                        headB = headB.next;
                        break;
                    case -1:
                        prior = headA;
                        headA = headA.next;
                        break;
                    default:
                        break;
                }
            }
            if (headB != null) {
                prior.next = headB;
            }
            return La;
        }
    }

    static class Main {
        public static void main(String[] args) {
            Object[] a = {1, 3, 4, 5, 9};
            Object[] b = {2, 4, 6, 10};
            PolynLinkedList AL = (PolynLinkedList) (new PolynLinkedList()).InitList(a);
            PolynLinkedList BL = (PolynLinkedList) (new PolynLinkedList()).InitList(b);
            AL.ListObjectraverse();
            System.out.println();
            BL.ListObjectraverse();
            /*AL.ListInsert(1, 0);
            System.out.println();
            System.out.println(AL.length);
            AL.ListDelete(4);
            AL.ListObjectraverse();*/
            System.out.println();
            MergerListOne((AL), BL).ListObjectraverse();
        }


        private static PolynLinkedList MergerList(PolynLinkedList La, PolynLinkedList Lb) {
            PolynLinkedList Lc = new PolynLinkedList();
            PolynListNode currentC = Lc.first;
            PolynListNode currentA = La.first.next;
            PolynListNode currentB = Lb.first.next;
            while (currentA != null && currentB != null) {
                if ((currentA.getVal().compareTo(currentB.getVal()) <= 0)) {
                    currentC.next = currentA;
                    currentA = currentA.next;
                } else {
                    currentC.next = currentB;
                    currentB = currentB.next;
                }
                currentC = currentC.next;
            }
            return Lc;
        }

        private static PolynLinkedList MergerListOne(PolynLinkedList La, PolynLinkedList Lb) {
            PolynListNode currentA = La.first.next;
            PolynListNode currentB = Lb.first.next;
            PolynListNode prior = La.first;
            while (currentA != null && currentB != null) {
                if ((currentA.getVal().compareTo(currentB.getVal()) <= 0)) {
                    PolynListNode insertNode = new PolynListNode(currentB.getVal());
                    prior.next = insertNode;
                    insertNode.next = currentA;
                    currentB = currentB.next;
                } else {
                    currentA = currentA.next;
                }
                prior = prior.next;
            }
            if (currentB != null) {
                prior.next = currentB;
            }
            return La;
        }

    }
}
